package org.zdw.data.structure.practice;

public class HeapPra {

    public void sort(int[] array){
        for(int i = array.length - 1 ; i > 0 ; i-- ){
            buildMaxHeap(array,i);
            swap(array,0,i);
        }
    }

    private void buildMaxHeap(int[] array , int lastIndex){
        for(int i = (lastIndex - 1) / 2 ; i >= 0 ; i--){
            int parentIndex = i ;
            int biggerIndex = 2*i + 1;
            if(biggerIndex < lastIndex){
                if(array[biggerIndex] < array[biggerIndex + 1]){
                    biggerIndex++;
                }
            }

            if(array[i] < array[biggerIndex]){
                swap(array,parentIndex,biggerIndex);
            }
        }
    }

    private void swap(int[] array,int i,int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}
